package com.example.demo.algorithm.sort.fast_sort;

/**
 * @author: htc
 * @date: Created in 13:34 2019/2/21.
 */
public class Demo3 {

    static int[] arr = {12, 20, 5, 16, 15, 1, 30, 45, 23, 9};

    public static void quickSort_1(int[] data, int start, int end) {
        if (data == null || start < 0 || end > data.length - 1) {
            throw new IllegalArgumentException("Invalid Parameters");
        }
        if (start == end) {
            return;
        }
        int index = partition(data, start, end);
        if (index > start) {
            quickSort_1(data, start, index - 1);
        }
        if (index < end) {
            quickSort_1(data, index + 1, end);
        }
    }

    public static void quickSort_2(int[] data, int start, int end) {
        if (data == null || start >= end) {
            return;
        }
        int i = start, j = end;
        int pivotKey = data[start];
        while (i < j) {
            while (i < j && data[j] >= pivotKey) {
                j--;
            }
            if (i < j) {
                data[i++] = data[j];
            }
            while (i < j && data[i] <= pivotKey) {
                i++;
            }
            if (i < j) {
                data[j--] = data[i];
            }
        }
        data[i] = pivotKey;
        quickSort_2(data, start, i - 1);
        quickSort_2(data, i + 1, end);
    }

    private static int partition(int[] data, int start, int end) {
        int index = start + (int) (Math.random() * (end - start + 1));
        swap(data, index, end);
        int small = start - 1;
        for (index = start; index < end; index++) {
            if (data[index] < data[end]) {
                small++;
                if (small != index) {
                    swap(data, index, small);
                }
            }
        }
        swap(data, small + 1, end);
        return small + 1;
    }

    private static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    public static void main(String[] args) {
//        quickSort_1(arr, 0, arr.length - 1);
        quickSort_2(arr, 0, arr.length - 1);
        for (int a : arr) {
            System.out.print(a + " ");
        }
    }
}
